/*
 * @lc app=leetcode.cn id=438 lang=typescript
 *
 * [438] 找到字符串中所有字母异位词
 */

// @lc code=start

//  思想：双指针
//  参考：https://labuladong.github.io/algo/2/19/51/

//  复杂度：O(n) O(n)

function findAnagrams(s: string, p: string): number[] {
    const res: number[] = []
    const need: Map<string, number> = new Map()
    const window: Map<string, number> = new Map()
    for (const c of p) {
        need.set(c, need.has(c) ? need.get(c)! + 1 : 1)
    }

    let left = 0, right = 0, valid = 0
    while (right < s.length) {
        const c = s[right]
        right++
        // 进行窗口内数据的一系列更新
        if (need.has(c)) {
            window.set(c, window.has(c) ? window.get(c)! + 1 : 1)
            if (window.get(c) === need.get(c)) {
                valid++
            }
        }

        // 判断左侧窗口是否要收缩
        while (right - left >= p.length) {
            // 当窗口符合条件时，把起始索引加入 res
            if (valid === need.size) {
                res.push(left)
            }
            const d = s[left]
            left++
            // 进行窗口内数据的一系列更新
            if (need.has(d)) {
                if (window.get(d) === need.get(d)) {
                    valid--
                }
                window.set(d, window.get(d)! - 1)
            }
        }
    }
    return res
};
// @lc code=end

console.log(findAnagrams('cbaebabacd', 'abc'))  // [0,6]
console.log(findAnagrams('abab', 'ab'))  // [0,1,2]
